package _线性;

import java.util.*;

public class _链表 {

    // 206:反转链表
    // 1——2——3——4——5
    // 从头部开始
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 92: 反转链表II 迭代法，画图模拟这个过程 https://leetcode.cn/problems/reverse-linked-list-ii/description/
    // 1——2——3——4——5
    public ListNode reverseBetween(ListNode head, int l, int r) {
        ListNode dummy = new ListNode(0, head), p = dummy;
        for (int i = 1; i < l; i++)
            p = p.next;                      // 1
        ListNode prev = null, cur = p.next;  // 2
        for (int i = 0; i < r - l + 1; i++) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;     // 5
        }
        p.next.next = cur;  // 1——2——5
        p.next = prev;      // 1——4

        return dummy.next;
    }

    // 25：K个一组翻转链表：https://leetcode.cn/problems/reverse-nodes-in-k-group/
    // 1——2 ——3——4 ——5
    // 2——1 ——4——3 ——5
    public ListNode reverseKGroup(ListNode head, int k) {
        // 检查当前是否有 k 个节点可供反转
        ListNode node = head;
        for (int i = 0; i < k; i++) {
            if (node == null) return head; // 不足 k 个，不反转
            node = node.next;
        }
        // 反转前 k 个节点
        ListNode prev = null,curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;        // 2
            curr = nextTemp;    // 3
        }
        // 递归处理后续链表，并将其接到当前反转部分的末尾
        head.next = reverseKGroup(curr, k);
        return prev;
    }

    // 2：两数相加（链表）：https://leetcode.cn/problems/add-two-numbers/
    // 2 —— 4 —— 3
    // 5 —— 6 —— 4
    // 7 —— 0 —— 8
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        int carry = 0; // 进位

        // 遍历两个链表
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry; // 初始化sum为进位

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        return dummy.next;
    }

    // 142:环形链表II: 找到环的起点：https://leetcode.cn/problems/linked-list-cycle-ii/description/
    public ListNode detectCycle(ListNode head) {
        ListNode s = head, f = head;
        ListNode index;
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
            if (s == f) {
                index = head;
                while (f != index) {
                    f = f.next;
                    index = index.next;
                }
                return index;
            }
        }
        return null;
    }

    // 160：相交链表： AB,BA,相交 或者 返回空
    public ListNode getIntersectionNode(ListNode A, ListNode B) {
        ListNode p1 = A, p2 = B;
        while (p1 != p2) {
            if (p1 == null) p1 = B;
            else p1 = p1.next;
            if (p2 == null) p2 = A;
            else p2 = p2.next;
        }
        return p1;
    }

    public ListNode LastK(ListNode head, int k) {
        ListNode s = head, f = head;
        // 先让快指针走k步
        for (int i = 0; i < k; i++) {
            f = f.next;
        }
        // 快慢指针一起走，直到快指针为空
        while (f != null) {
            f = f.next;
            s = s.next;
        }
        return s;
    }

    // 19：删除链表的倒数第 N 个节点: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
    // -1 —— 1 —— 1 —— 3 —— (4) —— 5
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode l = LastK(dummy, n + 1);
        l.next = l.next.next;
        return dummy.next;
    }

    // 2095：删除链表的中间节点：https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/
    // 维护一个 pre 即可
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode pre = null, s = head, f = head;
        // f != null && f.next != null               找的是偏左边的中间节点
        // f.next != null && f.next.next != null     s 节点多走了一步，找的是偏右边的中间节点
        while (f != null && f.next != null) {
            pre = s;
            s = s.next;
            f = f.next.next;
        }
        pre.next = s.next;
        return head;
    }

    // 203：移除链表的元素 6 6 6 6
    // 3217 从链表中移除数组中存在的数
    public ListNode removeElements(ListNode head, int val) {
        ListNode dumpy = new ListNode(-1, head), p = dumpy;
        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
            } else
                p = p.next;
        }
        return dumpy.next;
    }

    // 81：删除排序链表的重复元素（保留一个）https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
    // 直接操作 cur 节点
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode cur = head;
        while (cur.next != null) {
            // 检查当前节点是否有重复
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    //  82：删除排序链表的重复元素（直接删除） https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
    //  需要操作一个 pre 节点
    //  1 —— 1 —— 1 —— 2 —— 2 —— 3 —— 5
    //                           3 —— 5
    public ListNode deleteDuplicatesII(ListNode head) {
        ListNode dummy = new ListNode(0, head), prev = dummy, cur = head;
        while (cur != null) {
            // 检查当前节点是否有重复
            if (cur.next != null && cur.val == cur.next.val) {
                // 跳过所有重复的节点
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next; // 1
                }
                // 删除重复元素
                prev.next = cur.next; // 2
            } else {
                prev = prev.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

    // 2310：链表最大孪生和：https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/description/
    // 快慢指针将列表对半分，同时对慢指针反转列表
    public int pairSum(ListNode head) {
        // todo
        return 0;
    }

    // 23：合并k个升序链表：https://leetcode.cn/problems/merge-k-sorted-lists/
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode dumpy = new ListNode(-1), p = dumpy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            if (node.next != null)
                pq.add(node.next);
            p.next = node;
            p = p.next;
        }
        return dumpy.next;
    }


    // 排序链表
    // 递归，归并排序  递归终止条件//单层递归逻辑
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode mid = getMiddle(head);
        ListNode next = mid.next;
        // 断开链表
        mid.next = null;
        //将链表分为两半，对左右排序，再合并
        ListNode l = sortList(head);
        ListNode r = sortList(next);
        return merge(l, r);
    }

    // 合并两个已排序的链表
    private ListNode merge(ListNode l, ListNode r) {
        ListNode dummpy = new ListNode(-1), cur = dummpy;
        while (l != null && r != null) {
            if (l.val < r.val) {
                cur.next = l;
                l = l.next;
            } else {
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        if (l != null) {
            cur.next = l;
        }
        if (r != null) {
            cur.next = r;
        }
        return dummpy.next;
    }

    // 4 2 1 3
    private ListNode getMiddle(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode s = head, f = head;
        while (f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
        }
        return s;
    }
}






















